package day9;

import java.util.*;

public class code1 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        fun1(root,list);
        return list;
    }

    public void fun1(TreeNode node,List<Integer> list){
        if(node==null) return;
        fun1(node.left,list);
        list.add(node.val);
        fun1(node.right,list);
    }


    public TreeNode invertTree(TreeNode root) {
        fun2(root);
        return root;

    }

    public void fun2(TreeNode node){
        if(node==null) return;

        fun2(node.left);
        fun2(node.right);

        TreeNode n = node.left;
        node.left = node.right;
        node.right = n;

    }


    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;

        return fun3(root.left,root.right);
    }

    public boolean fun3(TreeNode left,TreeNode righ){
        if(left!=null&&righ!=null){
            if(left.val!=righ.val) return false;
        }else {
            if(left!=righ) return false;
        }

        return fun3(left.left,righ.right)&&fun3(left.right,righ.left);

    }


    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        fun4(root);
        return max;
    }

    public int fun4(TreeNode node){
        if(node==null) return 0;

        int lt = fun4(node.left);
        int rt = fun4(node.right);

        max = Math.max(max,lt+rt);
        return Math.max(lt,rt)+1;

    }


    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int len = queue.size();
            ArrayList<Integer> l = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode n = queue.poll();
                l.add(n.val);
                if(n.left!=null) queue.offer(n.left);
                if(n.right!=null) queue.offer(n.right);
            }
            list.add(l);
        }

        return list;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length==0) return null;
        int mid = nums.length/2;
        TreeNode root = new TreeNode(nums[mid]);

        fun5(root,nums,0,mid-1,mid+1,nums.length-1);

        return root;
    }

    public void fun5(TreeNode node, int[] nums, int l1, int r1, int l2, int r2){
        if(l1<=r1){
            int mid = (l1+r1)/2;
            TreeNode n = new TreeNode(nums[mid]);
            node.left = n;
            fun5(n,nums,l1,mid-1,mid+1,r1);
        }
        if(l2<=r2){
            int mid = (l2+r2)/2;
            TreeNode n = new TreeNode(nums[mid]);
            node.right = n;
            fun5(n,nums,l2,mid-1,mid+1,r2);
        }

    }







}
